//
// Created by wenyaxi on 24-10-28.
//

#include <unordered_map>
using namespace std;

class LRUCache {
private:
    struct Node {
        int value;
        int key;
        Node *next;
        Node *prev;

        Node(const int k, const int v) {
            key = k;
            value = v;
        }
    };

    int capacity;
    unordered_map<int, Node *> cache;
    Node *head;
    Node *tail;

public:
    LRUCache(int capacity) {
        head = new Node(0, 0);
        tail = head;
        head->next = tail;
        head->prev = tail;
        tail->next = head;
        tail->prev = head;
        this->capacity = capacity;
    }

    int get(int key) {
        if (!cache.contains(key)) {
            return -1;
        }
        auto node = cache[key];
        remove(node);
        addFirst(node);
        return node->value;
    }

    void put(int key, int value) {
        if (cache.contains(key)) {
            auto node = cache[key];
            node->value = value;
            get(key);
        } else if (!cache.contains(key) && cache.size() == capacity) {
            //不存在，已满
            int k = removeLast();
            cache.erase(k);
            put(key, value);
        } else if (!cache.contains(key) && cache.size() < capacity) {
            //不存在，未满
            auto node = new Node(key, value);
            cache[key] = node;
            addFirst(node);
        }
    }

    void addFirst(Node *node) {
        Node *then = head->next;
        head->next = node;
        node->prev = head;
        node->next = then;
        then->prev = node;
    }

    void remove(Node *node) {
        Node *prev = node->prev;
        Node *next = node->next;
        prev->next = next;
        next->prev = prev;
    }

    int removeLast() {
        auto node = tail->prev;
        auto prev = node->prev;
        prev->next = tail;
        tail->prev = prev;
        return node->key;
    }
};

int main() {
    LRUCache cache(2);
    cache.put(1, 1);
    cache.put(2, 2);
    cache.get(1);
    cache.put(3, 3);
    cache.get(2);
    cache.put(4, 4);
    cache.get(1);
    cache.get(3);
    cache.get(4);
    return 0;
}
